package 算法.LeetCode91.每日打卡题目;

import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import static 算法.LeetCode91.每日打卡题目.day17.deserialize;

/**
 * @author: 谢君臣
 * @create: 2021-02-17 17:29
 * @founction: XXXX
 */
public class day18 {
    public static void main(String[] args) {
        TreeNode treeNode = deserialize("[0,8,1,null,null,3,2,null,4,5,null,null,7,6]");
        List<List<Integer>> lists = verticalTraversal(treeNode);
        System.out.println(lists.toString());
    }
    public static List<List<Integer>> verticalTraversal(TreeNode root) {
        if (root==null)
            return null;
        List<List<Integer>> list = new ArrayList<>();
        List<A> da = new ArrayList<>();
        da = Traversal(root,0,0,da);
        Collections.sort(da,A::compareTo);
        int way = da.get(0).way;
        List<Integer> data = new ArrayList<>();
        for (A a : da) {
            if (a.way==way){
                data.add(a.data);
            }else {
                list.add(data);
                data = new ArrayList<>();
                data.clear();
                data.add(a.data);
                way = a.way;
            }
        }
        if (way!=da.get(0).way)
            list.add(data);
        return list;
    }

    private static List<A> Traversal(TreeNode root, int d,int i, List<A> da) {
        if (root!=null){
            da.add(new A(root.val,d,i));
            da = Traversal(root.left,d+1,i-1,da);
            da = Traversal(root.right,d+1,i+1,da);
        }
        return da;
    }

    public static class A implements Comparable<A>{
        public int data;
        public int depth;
        public int way;

        public A() {
        }

        public A(int data, int depth, int way) {
            this.data = data;
            this.depth = depth;
            this.way = way;
        }

        @Override
        public int compareTo(A o) {
            if (this.way != o.way)
                return Integer.compare(this.way, o.way);
            else if (this.depth != o.depth)
                return Integer.compare(this.depth, o.depth);
            else
                return Integer.compare(this.data, o.data);
        }
    }

}
